Modular arithmetic is concerned with the arithmetic of remainders from division.
Dividing %
) returns the remainder a % N
and the mathematical equivalent is
Mapping an integer
Two numbers are said to be congruent modulo
If there is an integer
Modulo division by
A group is simply a set
A group whose operation also supports commutativity (i.e.,
The order of a group, denoted by
The group operation
Additive notation uses the
Note that
Multiplicative notation denotes the group operation either by
Once again,
For all $a,b,c \in \mathbb{G}$, if $a\circ c = b \circ c$, then $a = b$ and in particular, if $ac = c$, then $a$ is the identity element of $\mathbb{G}$.
TODO
Interestingly, if the group is finite and
For any finite group $\mathbb{G}$ and element $g \in \mathbb{G}$, it holds that g^{|\mathbb{G}|} = 1$.
TODO
As a corollary of this, it turns out that applying the group operation to the same element more than
For any finite group $\mathbb{G}$ with $|\mathbb{G}| \gt 1$ and any $g \in \mathbb{G}$, it holds that $g^x = g^{[x \mod |\mathbb{G}|]}$
The abelian group
We would like to have a similar group but with multiplication modulo
We equip this set with the operation multiplication modulo
For any
We know for sure that
It is not hard to verify that
There are some interesting properties of such elements.
For any element $g$ of order $i$ in the finite group $\mathbb{G}$, it holds that $g^x = g^y$ if and only if $x = y \mod i$.
TODO
The order $i$ of any element $g$ in a finite group $\mathbb{G}$, must be a factor of the group order, i.e. $i | m$, where $m$ is the order of $\mathbb{G}$.
TODO
A group $\mathbb{G}$ is called *cyclic* if all of its elements can be obtained by applying the group operation repetitevely to *one* of its elements.
The group
Cyclic groups have some interesting properties.
Any group $\mathbb{G}$ with a prime order $p$ is cyclic and all of its elements, except for the identity, are its generators.
The group order $p$ *must* be divisible by the order $i$ of any element and so $i = p$ or $i = 1$. Only the identity element has order $1$ and so all the other elements must be of order $p$ and are therefore generators of the group.
An immediate corollary of this theorem is that the group